package leetcode.offer0070;

public class Solution {
	public int singleNonDuplicate(int[] nums) {
		if (nums.length == 1) {
			return nums[0];
		}
		int l = 0, r = nums.length - 1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (m == l || (nums[m - 1] != nums[m] && nums[m] != nums[m + 1])) {
				return nums[m];
			}
			if (nums[m - 1] == nums[m]) {
				if (((m - l + 1) & 1) == 0) {
					l = m + 1;
				} else {
					r = m - 2;
				}
			} else {
				if (((m - l + 2) & 1) == 0) {
					l = m + 2;
				} else {
					r = m - 1;
				}
			}
		}
		return -1;
	}
}
